package solutions.jianzhi;

import solutions.lib.BaseSolution;
import solutions.lib.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/7WHec2/">剑指 Offer II 077. 链表排序</a>
 */
public class Solution77 extends BaseSolution {

    public ListNode sortList(ListNode head) {
        PriorityQueue<ListNode> listNodes = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
        while (head != null) {
            listNodes.offer(head);
            head = head.next;
        }
        head = new ListNode();
        ListNode p = head;
        while (!listNodes.isEmpty()) {
            p.next = listNodes.poll();
            p = p.next;
        }
        return head.next;
    }

    public static void main(String[] args) {
        Solution77 solution = new Solution77();
    }
}